<?php
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val)
    {
        $this->val = $val;
    }
}

class Solution {
    /**
     * @$p1ram ListNode $headA
     * @$p1ram ListNode $headB
     * @return ListNode
     */
    function getIntersectionNode($headA, $headB) {
        if ($headA == null || $headB == null) {
            return null;
        }
        //先判断是否相交，不相交直接返回
        if(!$this->isIntersect($headA, $headB)){
            return null;
        }
        $p1 = $headA;
        $p2 = $headB;
        while ($p1 || $p2) {
            if ($p1 === $p2) {
                break;
            }
            $p1 = ($p1 == null) ? $headB : $p1->next;
            $p2 = ($p2 == null) ? $headA : $p2->next;
        }
        return $p1;
    }

    //判断是否相交
    function isIntersect($headA, $headB){
        if($headB == null || $headB == null){
            return false;
        }
        while($headA->next != null){
            $headA = $headA->next;
        }
        while($headB->next != null){
            $headB = $headB->next;
        }
        return $headA === $headB;
    }

    /**
     * public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
    pA = pA == null ? headB : pA.next;
    pB = pB == null ? headA : pB.next;
    }
    return pA;
    }
     */
}

/**
 * 创建两个指针 pApA 和 pBpB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。
当 pApA 到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pBpB 到达链表的尾部时，将它重定位到链表 A 的头结点。
若在某一时刻 pApA 和 pBpB 相遇，则 pApA/pBpB 为相交结点。
想弄清楚为什么这样可行, 可以考虑以下两个链表: A={1,3,5,7,9,11} 和 B={2,4,9,11}，相交于结点 9。 由于 B.length (=4) < A.length (=6)，pBpB 比 pApA 少经过 22 个结点，会先到达尾部。将 pBpB 重定向到 A 的头结点，pApA 重定向到 B 的头结点后，pBpB 要比 pApA 多走 2 个结点。因此，它们会同时到达交点。
如果两个链表存在相交，它们末尾的结点必然相同。因此当 pApA/pBpB 到达链表结尾时，记录下链表 A/B 对应的元素。若最后元素不相同，则两个链表不相交。
 */